COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00009 00003	.skip 1
C00010 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
.turn on "∂"
.cb ANOTHER SAMEFRINGE


	This SAMEFRINGE is simpler than those in the last two %2Newsletter%1s:
.skip 1
.begin nofill
(DE SAMEFRINGE (X Y) 
       (OR (EQ X Y)
	   (AND (NOT (ATOM X))
		(NOT (ATOM Y))
		(SAME (GOPHER X) (GOPHER Y)))))
 

(DE SAME (X Y) 
       (AND (EQ (CAR X) (CAR Y))
	    (SAMEFRINGE (CDR X) (CDR Y))))

(DE GOPHER (U) 
       (COND ((ATOM (CAR U)) U)
	     (T (GOPHER (CONS (CAAR U) (CONS (CDAR U) (CDR U))))))) 
.end

Here it is in a proposed LISP publication language:

%2samefringe[x, y] ← x %3eq %2y ∨ [¬%3at %2x ∧
¬%3at %2y ∧ same[gopher x, gopher y]]

%2same[x, y] ← %3a %2x %3eq a %3y ∧
%2samefringe[%3d %2 x, %3d %2y]

%2gopher u ← %3if at a %2u %3then%2 u
%3else%2 gopher %3aa %2u . [%3da %2u . %3d %2u]
%1
	%2gopher%1 digs up the first atom in an S-expression,
piling up the %2cdr%1 parts (with its hind legs) so that
indexing through the atoms can be resumed.  Because of shared structure,
the number of new cells in use in each argument at any time
(apart from those occupied by the original expression and assuming
iterative execution) is the number of
%2car%1s required to go from the top to the current atom -
usually a small fraction of the size of the S-expression.
If an argument of %2samefringe%1 is not elsewhere referenced,
its top level is forgotten and subject to garbage collection.

	A %2samefringe%1 using even less storage can be based on
the function %2residue[x,y]%1 that matches the successive atoms of ⊗x and ⊗y
and whose value gives the left-over atoms if there are any:
.skip 1
.begin nofill
%2residue[x, y] ← 
	qif x qeq y qthen %1T%2
	qelse qif qat x ∧ qat y qthen %1F%2
	qelse qif qat x qthen {gopher y}[λw.qif x qeq qa w qthen %1R%2 . qd w qelse %1F%2]
	qelse qif qat y qthen {gopher x}[λw.qif y qeq qa w qthen %1L%2 . qd w qelse %1F%2]
	qelse {residue[qa x,qa y]}[λw.
		qif w qeq %1F%2 qthen %1F%2
		qelse residue[qif qa w qeq %1L%2 qthen qd w . qd x qelse qd x,qif qa w qeq %1R%2 qthen qd w . qd y qelse qd y]]%1,
.end

where we put curly brackets around the arguments of a function
when we think it is clearer to put the arguments before the function.
Thus %2{x}f%1 is another way of writing %2f[x]%1.
It is a bit awkward to state exactly how much storage %2residue%1 uses.
This may be the same as the first algorithm given by Finin and Rutter,
but I found theirs hard to read, and these use no language extensions.

	I think all this shows that %2samefringe%1 is not an example of
the need for co-routines, and a new "simplest example" should be
found.	There is no merit in merely moving information from data
structure to control structure, and it makes some kinds of modification
harder.  Thus a game-playing algorithm that chooses the most
"cost-effective" node of the tree to extend can't have the usual simple
recursive structure.  A program with only assignments and %3go to%1s may
have the most easily modified control structure.  Of course, elegance,
understandability and a control logic admitting straightforward proofs of
correctness are also virtues.
.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of SAMEFR[F76,JMC]@SU-AI PUBbed at {time} on {date}.%1